package leetcode.median;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * ClassName: LRUCache
 * Description:
 * date: 2021-09-14 10:48
 *
 * @author liyifan
 */
public class LRUCache {

//    private int capacity;
//
//    private LinkedHashMap<Integer, Integer> map;
//
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
//            @Override
//            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
//                return this.size() > capacity;
//            }
//        };
//    }
//
//    public int get(int key) {
//        return map.getOrDefault(key, -1);
//    }
//
//    public void put(int key, int value) {
//        map.put(key, value);
//    }

    int size;
    int capacity;
    HashMap<Integer, Node> map;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.prev = tail;
        head.next = tail;
        tail.prev = head;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            int value = node.value;
            moveToTail(node);
            return value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.get(key) == null) {
            // 缓存中不存在
            Node node = new Node();
            node.key = key;
            node.value =  value;
            if (size < capacity) {
                // 小于capacity
                addToTail(node);
                size++;
            } else {
                int oldKey = removeHead();
                map.remove(oldKey);
                addToTail(node);
            }
            map.put(key, node);
        } else {
            // 缓存中已经存在
            Node node = map.get(key);
            node.value = value;
            moveToTail(node);
        }
    }

    private void addToTail(Node node){
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    private void moveToTail(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        addToTail(node);
    }

    private int remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        int key = node.key;
        node = null;
        return key;
    }

    private int removeHead(){
        Node node = head.next;
        int key = node.key;
        return remove(node);
    }

    private class Node{
        int key;
        int value;
        Node prev;
        Node next;
    }
}
